#pragma once

#include "utility.h"
#include "AVLTree.h"
#include "RBTree.h"
#include <initializer_list>

namespace qyc
{
	template<class K, class V, class Compare = less<K>>
	class map
	{
		typedef pair<const K, V> data_type;
		struct MapKeyOfValue
		{
			const K& operator()(const data_type& kv)
			{
				return kv.first;
			}
		};
		typedef RBTree<K, data_type, MapKeyOfValue, Compare> tree_type;
		typedef map<K, V, Compare> self;
	public:
		typedef typename tree_type::iterator iterator;
		typedef typename tree_type::const_iterator const_iterator;
		typedef typename tree_type::reverse_iterator reverse_iterator;
		typedef typename tree_type::const_reverse_iterator const_reverse_iterator;

		map() = default;
		template<class InputIterator>
		map(InputIterator first, InputIterator last)
		{
			_tree.insert_range(first, last);
		}
		map(std::initializer_list<data_type> _Ilist)
		{
			_tree.insert_range(_Ilist.begin(), _Ilist.end());
		}

		iterator begin()
		{
			return _tree.begin();
		}
		iterator end()
		{
			return _tree.end();
		}
		const_iterator begin() const
		{
			return _tree.begin();
		}
		const_iterator end() const
		{
			return _tree.end();
		}
		reverse_iterator rbegin()
		{
			return _tree.rbegin();
		}
		reverse_iterator rend()
		{
			return _tree.rend();
		}
		const_reverse_iterator rbegin() const
		{
			return _tree.rbegin();
		}
		const_reverse_iterator rend() const
		{
			return _tree.rend();
		}

		pair<iterator, bool> insert(const data_type& kv)
		{
			return _tree.insert(kv);
		}
		pair<iterator, bool> insert(data_type&& key)
		{
			return _tree.insert(qyc::forward<data_type>(key));
		}
		template <class... Args>
		pair<iterator, bool> emplace(Args&&... args)
		{
			return _tree.emplace(args...);
		}
		template<class InputIterator>
		void insert(InputIterator first, InputIterator last)
		{
			_tree.insert_range(first, last);
		}
		void erase(const K& key)
		{
			_tree.erase(key);
		}

		V& operator[](const K& key)
		{
			return (_tree.insert(data_type(key, V())).first)->second;
		}
		const V& operator[](const K& key) const
		{
			return (_tree.insert(data_type(key, V())).first)->second;
		}
		iterator find(const K& key)
		{
			return _tree.find(key);
		}
		const_iterator find(const K& key) const
		{
			return _tree.find(key);
		}
		
		void clear()
		{
			_tree.clear();
		}
		bool empty() const
		{
			return _tree.empty();
		}
		size_t size() const
		{
			return _tree.size();
		}
		void swap(self& des)
		{
			_tree.swap(des._tree);
		}
	private:
		tree_type _tree;
	};

	template<class K, class V, class Compare = less<K>>
	class multimap
	{
		typedef pair<const K, V> data_type;
		struct multiMapKeyOfValue
		{
			const K& operator()(const data_type& kv)
			{
				return kv.first;
			}
		};
		typedef RBTree<K, data_type, multiMapKeyOfValue, Compare> tree_type;
		typedef multimap<K, V, Compare> self;
	public:
		typedef typename tree_type::iterator iterator;
		typedef typename tree_type::const_iterator const_iterator;
		typedef typename tree_type::reverse_iterator reverse_iterator;
		typedef typename tree_type::const_reverse_iterator const_reverse_iterator;

		multimap() = default;
		template<class InputIterator>
		multimap(InputIterator first, InputIterator last)
		{
			_tree.insert_equal_range(first, last);
		}
		multimap(std::initializer_list<data_type> _Ilist)
		{
			_tree.insert_equal_range(_Ilist.begin(), _Ilist.end());
		}

		iterator begin()
		{
			return _tree.begin();
		}
		iterator end()
		{
			return _tree.end();
		}
		const_iterator begin() const
		{
			return _tree.begin();
		}
		const_iterator end() const
		{
			return _tree.end();
		}
		reverse_iterator rbegin()
		{
			return _tree.rbegin();
		}
		reverse_iterator rend()
		{
			return _tree.rend();
		}
		const_reverse_iterator rbegin() const
		{
			return _tree.rbegin();
		}
		const_reverse_iterator rend() const
		{
			return _tree.rend();
		}

		pair<iterator, bool> insert(const data_type& kv)
		{
			return _tree.insert_equal(kv);
		}
		pair<iterator, bool> insert(data_type&& key)
		{
			return _tree.insert_equal(qyc::forward<data_type>(key));
		}
		template <class... Args>
		pair<iterator, bool> emplace(Args&&... args)
		{
			return _tree.emplace_equal(args...);
		}
		template<class InputIterator>
		void insert(InputIterator first, InputIterator last)
		{
			_tree.insert_equal_range(first, last);
		}
		void erase(const K& key)
		{
			_tree.erase(key);
		}

		iterator find(const K& key)
		{
			return _tree.find(key);
		}
		const_iterator find(const K& key) const
		{
			return _tree.find(key);
		}

		void clear()
		{
			_tree.clear();
		}
		bool empty() const
		{
			return _tree.empty();
		}
		size_t size() const
		{
			return _tree.size();
		}
		void swap(self& des)
		{
			_tree.swap(des._tree);
		}
	private:
		tree_type _tree;
	};
}